/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 10836

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 50 61 74 68 3a 20 74 61 | 6e 6b 2e 6e 65 77 73 2e |Path: ta|nk.news.|
|00000010| 70 69 70 65 78 2e 6e 65 | 74 21 70 69 70 65 78 21 |pipex.ne|t!pipex!|
|00000020| 69 6f 6c 21 75 73 65 6e | 65 74 0a 46 72 6f 6d 3a |iol!usen|et.From:|
|00000030| 20 52 6f 79 20 4c 65 6f | 6e 61 72 64 20 3c 72 6c | Roy Leo|nard <rl|
|00000040| 65 6f 6e 61 72 64 40 66 | 65 72 72 6f 74 65 63 2e |eonard@f|errotec.|
|00000050| 69 65 3e 0a 4e 65 77 73 | 67 72 6f 75 70 73 3a 20 |ie>.News|groups: |
|00000060| 63 6f 6d 70 2e 6c 61 6e | 67 2e 63 0a 53 75 62 6a |comp.lan|g.c.Subj|
|00000070| 65 63 74 3a 20 52 65 3a | 20 42 69 74 20 43 6f 75 |ect: Re:| Bit Cou|
|00000080| 6e 74 69 6e 67 20 41 6c | 67 6f 72 69 74 68 6d 73 |nting Al|gorithms|
|00000090| 0a 44 61 74 65 3a 20 32 | 30 20 4d 61 72 20 31 39 |.Date: 2|0 Mar 19|
|000000a0| 39 36 20 31 30 3a 32 30 | 3a 32 38 20 47 4d 54 0a |96 10:20|:28 GMT.|
|000000b0| 4f 72 67 61 6e 69 7a 61 | 74 69 6f 6e 3a 20 46 65 |Organiza|tion: Fe|
|000000c0| 72 72 6f 74 65 63 20 4c | 74 64 0a 4d 65 73 73 61 |rrotec L|td.Messa|
|000000d0| 67 65 2d 49 44 3a 20 3c | 34 69 6f 6d 35 63 24 34 |ge-ID: <|4iom5c$4|
|000000e0| 64 65 40 6e 75 61 63 68 | 74 2e 69 6f 6c 2e 69 65 |de@nuach|t.iol.ie|
|000000f0| 3e 0a 4e 4e 54 50 2d 50 | 6f 73 74 69 6e 67 2d 48 |>.NNTP-P|osting-H|
|00000100| 6f 73 74 3a 20 66 65 72 | 72 6f 74 65 63 2e 69 6f |ost: fer|rotec.io|
|00000110| 6c 2e 69 65 0a 4d 69 6d | 65 2d 56 65 72 73 69 6f |l.ie.Mim|e-Versio|
|00000120| 6e 3a 20 31 2e 30 0a 43 | 6f 6e 74 65 6e 74 2d 54 |n: 1.0.C|ontent-T|
|00000130| 79 70 65 3a 20 74 65 78 | 74 2f 70 6c 61 69 6e 3b |ype: tex|t/plain;|
|00000140| 20 63 68 61 72 73 65 74 | 3d 75 73 2d 61 73 63 69 | charset|=us-asci|
|00000150| 69 0a 43 6f 6e 74 65 6e | 74 2d 54 72 61 6e 73 66 |i.Conten|t-Transf|
|00000160| 65 72 2d 45 6e 63 6f 64 | 69 6e 67 3a 20 37 62 69 |er-Encod|ing: 7bi|
|00000170| 74 0a 58 2d 4d 61 69 6c | 65 72 3a 20 4d 6f 7a 69 |t.X-Mail|er: Mozi|
|00000180| 6c 6c 61 20 31 2e 32 32 | 20 28 57 69 6e 64 6f 77 |lla 1.22| (Window|
|00000190| 73 3b 20 49 3b 20 31 36 | 62 69 74 29 0a 54 6f 3a |s; I; 16|bit).To:|
|000001a0| 20 67 74 6e 40 65 62 74 | 2e 63 6f 6d 2c 77 6b 61 | gtn@ebt|.com,wka|
|000001b0| 75 66 6d 61 6e 40 75 73 | 2e 6f 72 61 63 6c 65 2e |ufman@us|.oracle.|
|000001c0| 63 6f 6d 2c 64 61 72 72 | 65 6c 6c 2e 67 72 61 69 |com,darr|ell.grai|
|000001d0| 6e 67 65 72 40 75 74 6f | 72 6f 6e 74 6f 2e 63 6f |nger@uto|ronto.co|
|000001e0| 6d 0a 0a 0a 54 68 61 6e | 6b 73 20 61 6c 6c 21 0a |m...Than|ks all!.|
|000001f0| 0a 49 20 72 65 63 65 69 | 76 65 64 20 71 75 69 74 |.I recei|ved quit|
|00000200| 65 20 61 20 66 65 77 20 | 72 65 70 6c 69 65 73 20 |e a few |replies |
|00000210| 74 6f 20 6d 79 20 71 75 | 65 72 79 20 61 62 6f 75 |to my qu|ery abou|
|00000220| 74 20 62 69 74 20 63 6f | 75 6e 74 69 6e 67 20 61 |t bit co|unting a|
|00000230| 6c 67 6f 72 69 74 68 6d | 73 2e 20 0a 20 57 68 61 |lgorithm|s. . Wha|
|00000240| 74 0a 66 6f 6c 6c 6f 77 | 73 20 69 73 20 61 20 62 |t.follow|s is a b|
|00000250| 72 69 65 66 20 73 75 6d | 6d 61 72 79 20 6f 66 20 |rief sum|mary of |
|00000260| 74 68 65 20 72 65 70 6c | 69 65 73 20 49 20 72 65 |the repl|ies I re|
|00000270| 63 65 69 76 65 64 20 66 | 6f 72 20 77 68 69 63 68 |ceived f|or which|
|00000280| 20 49 20 61 6d 20 74 72 | 75 6c 79 0a 67 72 61 74 | I am tr|uly.grat|
|00000290| 65 66 75 6c 2e 0a 0a 54 | 68 65 20 67 65 6e 65 72 |eful...T|he gener|
|000002a0| 61 6c 20 63 6f 6e 73 65 | 6e 73 75 73 20 73 65 65 |al conse|nsus see|
|000002b0| 6d 73 20 74 6f 20 62 65 | 20 74 68 61 74 20 61 20 |ms to be| that a |
|000002c0| 6c 6f 6f 6b 75 70 20 74 | 61 62 6c 65 20 69 73 20 |lookup t|able is |
|000002d0| 74 68 65 20 66 61 73 74 | 65 73 74 20 61 6e 64 0a |the fast|est and.|
|000002e0| 65 61 73 69 65 73 74 20 | 6d 65 74 68 6f 64 20 74 |easiest |method t|
|000002f0| 6f 20 69 6d 70 6c 65 6d | 65 6e 74 2e 20 20 54 68 |o implem|ent.  Th|
|00000300| 69 73 20 70 69 65 63 65 | 20 6f 66 20 63 6f 64 65 |is piece| of code|
|00000310| 20 66 72 6f 6d 20 47 61 | 76 69 6e 20 4e 69 63 6f | from Ga|vin Nico|
|00000320| 6c 20 0a 28 67 74 6e 40 | 65 62 74 2e 63 6f 6d 29 |l .(gtn@|ebt.com)|
|00000330| 0a 64 65 6d 6f 6e 73 74 | 72 61 74 65 73 20 74 68 |.demonst|rates th|
|00000340| 69 73 20 61 6c 67 6f 72 | 69 74 68 6d 3a 0a 0a 2a |is algor|ithm:..*|
|00000350| 2a 2a 0a 2a 2a 2a 0a 0a | 49 66 20 79 6f 75 20 6b |**.***..|If you k|
|00000360| 6e 6f 77 20 74 68 65 20 | 73 69 7a 65 20 6f 66 20 |now the |size of |
|00000370| 74 68 65 20 64 61 74 61 | 20 74 68 61 74 20 79 6f |the data| that yo|
|00000380| 75 20 61 72 65 20 74 72 | 79 69 6e 67 20 74 6f 20 |u are tr|ying to |
|00000390| 63 6f 75 6e 74 20 62 69 | 74 73 20 69 6e 2c 0a 0a |count bi|ts in,..|
|000003a0| 61 20 73 69 6d 70 6c 65 | 20 77 61 79 20 69 73 20 |a simple| way is |
|000003b0| 74 6f 20 75 73 65 20 61 | 20 74 61 62 6c 65 2e 20 |to use a| table. |
|000003c0| 54 68 69 73 20 69 73 20 | 61 6c 73 6f 20 71 75 69 |This is |also qui|
|000003d0| 74 65 20 66 61 73 74 2e | 0a 0a 0a 0a 2f 2a 0a 0a |te fast.|..../*..|
|000003e0| 20 2a 20 63 6f 75 6e 74 | 20 62 69 74 73 20 75 73 | * count| bits us|
|000003f0| 69 6e 67 20 61 20 74 61 | 62 6c 65 0a 0a 20 2a 2f |ing a ta|ble.. */|
|00000400| 0a 0a 20 0a 0a 73 74 61 | 74 69 63 20 63 68 61 72 |.. ..sta|tic char|
|00000410| 20 62 69 74 5f 74 61 62 | 6c 65 5b 32 35 36 5d 20 | bit_tab|le[256] |
|00000420| 3d 20 7b 0a 0a 20 20 30 | 2c 20 31 2c 20 31 2c 20 |= {..  0|, 1, 1, |
|00000430| 32 2c 20 31 2c 20 32 2c | 20 32 2c 20 33 2c 20 31 |2, 1, 2,| 2, 3, 1|
|00000440| 2c 20 32 2c 20 32 2c 20 | 33 2c 20 32 2c 20 33 2c |, 2, 2, |3, 2, 3,|
|00000450| 20 33 2c 20 34 2c 0a 0a | 20 20 31 2c 20 32 2c 20 | 3, 4,..|  1, 2, |
|00000460| 32 2c 20 33 2c 20 32 2c | 20 33 2c 20 33 2c 20 34 |2, 3, 2,| 3, 3, 4|
|00000470| 2c 20 32 2c 20 33 2c 20 | 33 2c 20 34 2c 20 33 2c |, 2, 3, |3, 4, 3,|
|00000480| 20 34 2c 20 34 2c 20 35 | 2c 0a 0a 20 20 31 2c 20 | 4, 4, 5|,..  1, |
|00000490| 32 2c 20 32 2c 20 33 2c | 20 32 2c 20 33 2c 20 33 |2, 2, 3,| 2, 3, 3|
|000004a0| 2c 20 34 2c 20 32 2c 20 | 33 2c 20 33 2c 20 34 2c |, 4, 2, |3, 3, 4,|
|000004b0| 20 33 2c 20 34 2c 20 34 | 2c 20 35 2c 0a 0a 20 20 | 3, 4, 4|, 5,..  |
|000004c0| 32 2c 20 33 2c 20 33 2c | 20 34 2c 20 33 2c 20 34 |2, 3, 3,| 4, 3, 4|
|000004d0| 2c 20 34 2c 20 35 2c 20 | 33 2c 20 34 2c 20 34 2c |, 4, 5, |3, 4, 4,|
|000004e0| 20 35 2c 20 34 2c 20 35 | 2c 20 35 2c 20 36 2c 0a | 5, 4, 5|, 5, 6,.|
|000004f0| 0a 20 20 31 2c 20 32 2c | 20 32 2c 20 33 2c 20 32 |.  1, 2,| 2, 3, 2|
|00000500| 2c 20 33 2c 20 33 2c 20 | 34 2c 20 32 2c 20 33 2c |, 3, 3, |4, 2, 3,|
|00000510| 20 33 2c 20 34 2c 20 33 | 2c 20 34 2c 20 34 2c 20 | 3, 4, 3|, 4, 4, |
|00000520| 35 2c 0a 0a 20 20 32 2c | 20 33 2c 20 33 2c 20 34 |5,..  2,| 3, 3, 4|
|00000530| 2c 20 33 2c 20 34 2c 20 | 34 2c 20 35 2c 20 33 2c |, 3, 4, |4, 5, 3,|
|00000540| 20 34 2c 20 34 2c 20 35 | 2c 20 34 2c 20 35 2c 20 | 4, 4, 5|, 4, 5, |
|00000550| 35 2c 20 36 2c 0a 0a 20 | 20 32 2c 20 33 2c 20 33 |5, 6,.. | 2, 3, 3|
|00000560| 2c 20 34 2c 20 33 2c 20 | 34 2c 20 34 2c 20 35 2c |, 4, 3, |4, 4, 5,|
|00000570| 20 33 2c 20 34 2c 20 34 | 2c 20 35 2c 20 34 2c 20 | 3, 4, 4|, 5, 4, |
|00000580| 35 2c 20 35 2c 20 36 2c | 0a 0a 20 20 33 2c 20 34 |5, 5, 6,|..  3, 4|
|00000590| 2c 20 34 2c 20 35 2c 20 | 34 2c 20 35 2c 20 35 2c |, 4, 5, |4, 5, 5,|
|000005a0| 20 36 2c 20 34 2c 20 35 | 2c 20 35 2c 20 36 2c 20 | 6, 4, 5|, 5, 6, |
|000005b0| 35 2c 20 36 2c 20 36 2c | 20 37 2c 0a 0a 20 20 31 |5, 6, 6,| 7,..  1|
|000005c0| 2c 20 32 2c 20 32 2c 20 | 33 2c 20 32 2c 20 33 2c |, 2, 2, |3, 2, 3,|
|000005d0| 20 33 2c 20 34 2c 20 32 | 2c 20 33 2c 20 33 2c 20 | 3, 4, 2|, 3, 3, |
|000005e0| 34 2c 20 33 2c 20 34 2c | 20 34 2c 20 35 2c 0a 0a |4, 3, 4,| 4, 5,..|
|000005f0| 20 20 32 2c 20 33 2c 20 | 33 2c 20 34 2c 20 33 2c |  2, 3, |3, 4, 3,|
|00000600| 20 34 2c 20 34 2c 20 35 | 2c 20 33 2c 20 34 2c 20 | 4, 4, 5|, 3, 4, |
|00000610| 34 2c 20 35 2c 20 34 2c | 20 35 2c 20 35 2c 20 36 |4, 5, 4,| 5, 5, 6|
|00000620| 2c 0a 0a 20 20 32 2c 20 | 33 2c 20 33 2c 20 34 2c |,..  2, |3, 3, 4,|
|00000630| 20 33 2c 20 34 2c 20 34 | 2c 20 35 2c 20 33 2c 20 | 3, 4, 4|, 5, 3, |
|00000640| 34 2c 20 34 2c 20 35 2c | 20 34 2c 20 35 2c 20 35 |4, 4, 5,| 4, 5, 5|
|00000650| 2c 20 36 2c 0a 0a 20 20 | 33 2c 20 34 2c 20 34 2c |, 6,..  |3, 4, 4,|
|00000660| 20 35 2c 20 34 2c 20 35 | 2c 20 35 2c 20 36 2c 20 | 5, 4, 5|, 5, 6, |
|00000670| 34 2c 20 35 2c 20 35 2c | 20 36 2c 20 35 2c 20 36 |4, 5, 5,| 6, 5, 6|
|00000680| 2c 20 36 2c 20 37 2c 0a | 0a 20 20 32 2c 20 33 2c |, 6, 7,.|.  2, 3,|
|00000690| 20 33 2c 20 34 2c 20 33 | 2c 20 34 2c 20 34 2c 20 | 3, 4, 3|, 4, 4, |
|000006a0| 35 2c 20 33 2c 20 34 2c | 20 34 2c 20 35 2c 20 34 |5, 3, 4,| 4, 5, 4|
|000006b0| 2c 20 35 2c 20 35 2c 20 | 36 2c 0a 0a 20 20 33 2c |, 5, 5, |6,..  3,|
|000006c0| 20 34 2c 20 34 2c 20 35 | 2c 20 34 2c 20 35 2c 20 | 4, 4, 5|, 4, 5, |
|000006d0| 35 2c 20 36 2c 20 34 2c | 20 35 2c 20 35 2c 20 36 |5, 6, 4,| 5, 5, 6|
|000006e0| 2c 20 35 2c 20 36 2c 20 | 36 2c 20 37 2c 0a 0a 20 |, 5, 6, |6, 7,.. |
|000006f0| 20 33 2c 20 34 2c 20 34 | 2c 20 35 2c 20 34 2c 20 | 3, 4, 4|, 5, 4, |
|00000700| 35 2c 20 35 2c 20 36 2c | 20 34 2c 20 35 2c 20 35 |5, 5, 6,| 4, 5, 5|
|00000710| 2c 20 36 2c 20 35 2c 20 | 36 2c 20 36 2c 20 37 2c |, 6, 5, |6, 6, 7,|
|00000720| 0a 0a 20 20 34 2c 20 35 | 2c 20 35 2c 20 36 2c 20 |..  4, 5|, 5, 6, |
|00000730| 35 2c 20 36 2c 20 36 2c | 20 37 2c 20 35 2c 20 36 |5, 6, 6,| 7, 5, 6|
|00000740| 2c 20 36 2c 20 37 2c 20 | 36 2c 20 37 2c 20 37 2c |, 6, 7, |6, 7, 7,|
|00000750| 20 38 2c 0a 0a 7d 3b 0a | 0a 20 0a 0a 69 6e 74 20 | 8,..};.|. ..int |
|00000760| 63 6f 75 6e 74 5f 62 69 | 74 73 5f 74 61 62 6c 65 |count_bi|ts_table|
|00000770| 28 75 6e 73 69 67 6e 65 | 64 20 6c 6f 6e 67 20 78 |(unsigne|d long x|
|00000780| 29 0a 0a 7b 0a 0a 20 20 | 20 20 75 6e 73 69 67 6e |)..{..  |  unsign|
|00000790| 65 64 20 63 68 61 72 20 | 2a 70 74 72 20 3d 20 28 |ed char |*ptr = (|
|000007a0| 75 6e 73 69 67 6e 65 64 | 20 63 68 61 72 20 2a 29 |unsigned| char *)|
|000007b0| 26 78 3b 0a 0a 20 0a 0a | 20 20 20 20 72 65 74 75 |&x;.. ..|    retu|
|000007c0| 72 6e 28 62 69 74 5f 74 | 61 62 6c 65 5b 70 74 72 |rn(bit_t|able[ptr|
|000007d0| 5b 30 5d 5d 20 2b 20 62 | 69 74 5f 74 61 62 6c 65 |[0]] + b|it_table|
|000007e0| 5b 70 74 72 5b 31 5d 5d | 20 2b 20 0a 0a 20 20 20 |[ptr[1]]| + ..   |
|000007f0| 20 20 20 20 20 20 20 20 | 62 69 74 5f 74 61 62 6c |        |bit_tabl|
|00000800| 65 5b 70 74 72 5b 32 5d | 5d 20 2b 20 62 69 74 5f |e[ptr[2]|] + bit_|
|00000810| 74 61 62 6c 65 5b 70 74 | 72 5b 33 5d 5d 20 29 3b |table[pt|r[3]] );|
|00000820| 0a 0a 7d 0a 2a 2a 2a 0a | 2a 2a 2a 0a 48 65 20 68 |..}.***.|***.He h|
|00000830| 61 73 20 61 6c 73 6f 20 | 64 69 73 63 6f 76 65 72 |as also |discover|
|00000840| 65 64 2c 20 77 68 61 74 | 20 68 65 20 64 65 73 63 |ed, what| he desc|
|00000850| 72 69 62 65 73 20 61 73 | 20 74 68 65 20 6d 6f 73 |ribes as| the mos|
|00000860| 74 20 65 73 6f 74 65 72 | 69 63 20 6f 6e 65 2e 2e |t esoter|ic one..|
|00000870| 2e 0a 2e 2e 49 20 68 61 | 76 65 20 65 76 65 72 20 |....I ha|ve ever |
|00000880| 73 65 65 6e 20 69 73 20 | 48 41 43 4b 4d 45 4d 2c |seen is |HACKMEM,|
|00000890| 20 66 6f 72 20 58 31 31 | 20 73 6f 75 72 63 65 20 | for X11| source |
|000008a0| 63 6f 64 65 3a 0a 0a 0a | 0a 0a 69 6e 74 20 63 6f |code:...|..int co|
|000008b0| 75 6e 74 5f 62 69 74 73 | 5f 68 61 63 6b 6d 65 6d |unt_bits|_hackmem|
|000008c0| 28 75 6e 73 69 67 6e 65 | 64 20 6c 6f 6e 67 20 78 |(unsigne|d long x|
|000008d0| 29 0a 0a 7b 0a 0a 20 20 | 20 20 72 65 67 69 73 74 |)..{..  |  regist|
|000008e0| 65 72 20 75 6e 73 69 67 | 6e 65 64 20 6c 6f 6e 67 |er unsig|ned long|
|000008f0| 20 74 6d 70 3b 0a 0a 20 | 0a 0a 20 20 20 20 74 6d | tmp;.. |..    tm|
|00000900| 70 20 3d 20 28 78 20 3e | 3e 20 31 29 20 26 30 33 |p = (x >|> 1) &03|
|00000910| 33 33 33 33 33 33 33 33 | 33 33 3b 0a 0a 20 20 20 |33333333|33;..   |
|00000920| 20 74 6d 70 20 3d 20 78 | 20 2d 20 74 6d 70 20 2d | tmp = x| - tmp -|
|00000930| 20 28 28 74 6d 70 20 3e | 3e 31 29 20 26 20 30 33 | ((tmp >|>1) & 03|
|00000940| 33 33 33 33 33 33 33 33 | 33 33 29 3b 0a 0a 20 20 |33333333|33);..  |
|00000950| 20 20 72 65 74 75 72 6e | 20 28 28 75 6e 73 69 67 |  return| ((unsig|
|00000960| 6e 65 64 20 69 6e 74 29 | 20 28 28 28 74 6d 70 20 |ned int)| (((tmp |
|00000970| 2b 20 28 74 6d 70 20 3e | 3e 20 33 29 29 20 26 20 |+ (tmp >|> 3)) & |
|00000980| 30 33 30 37 30 37 30 37 | 30 37 30 37 29 20 25 20 |03070707|0707) % |
|00000990| 30 37 37 29 29 3b 0a 0a | 7d 0a 2a 2a 2a 0a 2a 2a |077));..|}.***.**|
|000009a0| 2a 0a 0a 57 68 69 63 68 | 20 77 6f 72 6b 73 20 72 |*..Which| works r|
|000009b0| 65 6d 61 72 6b 61 62 6c | 79 20 77 65 6c 6c 20 6f |emarkabl|y well o|
|000009c0| 6e 20 61 20 50 43 2e 20 | 20 49 20 73 74 69 6c 6c |n a PC. | I still|
|000009d0| 20 68 61 76 65 6e 27 74 | 20 77 6f 72 6b 65 64 20 | haven't| worked |
|000009e0| 6f 75 74 20 0a 70 72 65 | 63 69 73 65 6c 79 0a 68 |out .pre|cisely.h|
|000009f0| 6f 77 20 69 74 20 77 6f | 72 6b 73 2c 20 62 75 74 |ow it wo|rks, but|
|00000a00| 20 61 20 70 65 6e 20 61 | 6e 64 20 61 20 70 69 65 | a pen a|nd a pie|
|00000a10| 63 65 20 6f 66 20 70 61 | 70 65 72 20 77 69 6c 6c |ce of pa|per will|
|00000a20| 20 73 6f 6c 76 65 20 74 | 68 61 74 3b 29 0a 0a 54 | solve t|hat;)..T|
|00000a30| 68 65 20 66 6f 6c 6c 6f | 77 69 6e 67 20 64 65 73 |he follo|wing des|
|00000a40| 63 72 69 70 74 69 6f 6e | 20 63 61 6d 65 20 66 72 |cription| came fr|
|00000a50| 6f 6d 20 57 69 6c 6c 69 | 61 6d 20 4b 61 75 66 6d |om Willi|am Kaufm|
|00000a60| 61 6e 20 0a 3c 77 6b 61 | 75 66 6d 61 6e 40 75 73 |an .<wka|ufman@us|
|00000a70| 2e 6f 72 61 63 6c 65 2e | 63 6f 6d 3e 0a 77 68 6f |.oracle.|com>.who|
|00000a80| 20 77 61 73 20 61 6c 73 | 6f 20 68 6f 72 72 69 66 | was als|o horrif|
|00000a90| 69 65 64 20 61 74 20 74 | 68 65 20 70 6f 73 73 69 |ied at t|he possi|
|00000aa0| 62 69 6c 69 74 79 20 74 | 68 61 74 20 49 20 6d 69 |bility t|hat I mi|
|00000ab0| 67 68 74 20 74 72 79 20 | 61 73 73 65 6d 62 6c 65 |ght try |assemble|
|00000ac0| 72 20 74 6f 0a 73 6f 6c | 76 65 20 74 68 69 73 20 |r to.sol|ve this |
|00000ad0| 70 72 6f 62 6c 65 6d 2e | 20 20 48 65 20 72 65 66 |problem.|  He ref|
|00000ae0| 65 72 72 65 64 20 6d 65 | 20 74 6f 20 74 68 65 20 |erred me| to the |
|00000af0| 43 20 46 41 51 20 28 51 | 32 30 2e 31 33 2c 20 61 |C FAQ (Q|20.13, a|
|00000b00| 6e 64 20 6f 74 68 65 72 | 73 29 2e 0a 0a 2a 2a 2a |nd other|s)...***|
|00000b10| 0a 2a 2a 2a 0a 0a 20 20 | 20 20 49 66 20 79 6f 75 |.***..  |  If you|
|00000b20| 20 63 61 6e 20 61 66 66 | 6f 72 64 20 74 68 65 20 | can aff|ord the |
|00000b30| 6d 65 6d 6f 72 79 2c 20 | 79 6f 75 20 63 6f 75 6c |memory, |you coul|
|00000b40| 64 20 64 65 66 69 6e 65 | 20 61 20 28 32 5e 43 48 |d define| a (2^CH|
|00000b50| 41 52 5f 42 49 54 29 2d | 62 79 74 65 20 0a 61 72 |AR_BIT)-|byte .ar|
|00000b60| 72 61 79 0a 77 68 65 72 | 65 20 65 61 63 68 20 61 |ray.wher|e each a|
|00000b70| 72 72 61 79 5b 58 5d 20 | 69 73 20 74 68 65 20 6e |rray[X] |is the n|
|00000b80| 75 6d 62 65 72 20 6f 66 | 20 22 6f 6e 22 20 62 69 |umber of| "on" bi|
|00000b90| 74 73 20 69 6e 20 58 2e | 20 20 54 68 65 6e 2c 20 |ts in X.|  Then, |
|00000ba0| 79 6f 75 27 64 20 6a 75 | 73 74 0a 77 61 6c 6b 20 |you'd ju|st.walk |
|00000bb0| 74 68 72 6f 75 67 68 20 | 74 68 65 20 61 72 72 61 |through |the arra|
|00000bc0| 79 20 61 6e 64 20 61 64 | 64 20 74 68 65 20 62 69 |y and ad|d the bi|
|00000bd0| 74 20 73 75 6d 73 20 61 | 73 20 79 6f 75 20 67 6f |t sums a|s you go|
|00000be0| 2e 0a 0a 20 20 20 20 49 | 66 20 79 6f 75 20 63 61 |...    I|f you ca|
|00000bf0| 6e 27 74 20 73 70 61 72 | 65 20 28 32 5e 43 48 41 |n't spar|e (2^CHA|
|00000c00| 52 5f 42 49 54 29 20 62 | 79 74 65 73 2c 20 79 6f |R_BIT) b|ytes, yo|
|00000c10| 75 20 63 6f 75 6c 64 20 | 6d 61 6b 65 20 61 20 73 |u could |make a s|
|00000c20| 69 6d 69 6c 61 72 0a 28 | 32 5e 28 43 48 41 52 5f |imilar.(|2^(CHAR_|
|00000c30| 42 49 54 2f 32 29 29 2d | 62 79 74 65 20 61 72 72 |BIT/2))-|byte arr|
|00000c40| 61 79 2c 20 61 6e 64 2c | 20 66 6f 72 20 65 61 63 |ay, and,| for eac|
|00000c50| 68 20 69 6e 70 75 74 20 | 62 79 74 65 20 28 75 6e |h input |byte (un|
|00000c60| 73 69 67 6e 65 64 20 63 | 68 61 72 29 20 58 2c 0a |signed c|har) X,.|
|00000c70| 75 73 65 0a 0a 20 20 20 | 20 20 20 20 20 61 72 72 |use..   |     arr|
|00000c80| 61 79 5b 58 20 26 20 28 | 28 31 20 3c 3c 20 28 43 |ay[X & (|(1 << (C|
|00000c90| 48 41 52 5f 42 49 54 2f | 32 29 29 2d 31 29 5d 20 |HAR_BIT/|2))-1)] |
|00000ca0| 2b 20 61 72 72 61 79 5b | 58 20 3e 3e 20 28 43 48 |+ array[|X >> (CH|
|00000cb0| 41 52 5f 42 49 54 2f 32 | 29 5d 3b 0a 0a 28 54 68 |AR_BIT/2|)];..(Th|
|00000cc0| 65 20 22 28 28 31 20 3c | 3c 20 28 43 48 41 52 5f |e "((1 <|< (CHAR_|
|00000cd0| 42 49 54 2f 32 29 29 2d | 31 29 22 20 67 65 74 73 |BIT/2))-|1)" gets|
|00000ce0| 20 28 43 48 41 52 5f 42 | 49 54 2f 32 29 20 62 69 | (CHAR_B|IT/2) bi|
|00000cf0| 74 73 20 69 6e 20 74 68 | 65 20 6c 6f 77 0a 68 61 |ts in th|e low.ha|
|00000d00| 6c 66 2d 63 68 61 72 3b | 20 74 68 65 20 65 78 70 |lf-char;| the exp|
|00000d10| 72 65 73 73 69 6f 6e 20 | 67 65 74 73 20 74 68 65 |ression |gets the|
|00000d20| 20 72 65 6d 61 69 6e 64 | 65 72 20 6f 66 20 58 2f | remaind|er of X/|
|00000d30| 28 32 5e 28 43 48 41 52 | 5f 42 49 54 2f 32 29 29 |(2^(CHAR|_BIT/2))|
|00000d40| 2e 29 0a 0a 2a 2a 2a 0a | 2a 2a 2a 0a 0a 44 61 72 |.)..***.|***..Dar|
|00000d50| 72 65 6c 6c 20 47 72 61 | 69 6e 67 65 72 20 3c 64 |rell Gra|inger <d|
|00000d60| 61 72 72 65 6c 6c 2e 67 | 72 61 69 6e 67 65 72 40 |arrell.g|rainger@|
|00000d70| 75 74 6f 72 6f 6e 74 6f | 2e 63 61 3e 20 73 65 6e |utoronto|.ca> sen|
|00000d80| 74 20 74 68 65 20 66 6f | 6c 6c 6f 77 69 6e 67 20 |t the fo|llowing |
|00000d90| 72 65 70 6c 79 0a 0a 0a | 23 69 6e 63 6c 75 64 65 |reply...|#include|
|00000da0| 20 3c 6c 69 6d 69 74 73 | 2e 68 3e 0a 0a 2f 2a 20 | <limits|.h>../* |
|00000db0| 69 6e 70 75 74 3a 20 61 | 72 72 61 79 09 2d 20 70 |input: a|rray.- p|
|00000dc0| 6f 69 6e 74 65 72 20 74 | 6f 20 74 68 65 20 61 72 |ointer t|o the ar|
|00000dd0| 72 61 79 20 6f 66 20 6c | 6f 6e 67 20 69 6e 74 73 |ray of l|ong ints|
|00000de0| 0a 09 20 20 73 69 7a 65 | 09 2d 20 6e 75 6d 62 65 |..  size|.- numbe|
|00000df0| 72 20 6f 66 20 65 6c 65 | 6d 65 6e 74 73 20 69 6e |r of ele|ments in|
|00000e00| 20 61 72 72 61 79 0a 2a | 2f 0a 75 6e 73 69 67 6e | array.*|/.unsign|
|00000e10| 65 64 20 6c 6f 6e 67 20 | 69 6e 74 20 63 6f 75 6e |ed long |int coun|
|00000e20| 74 5f 62 69 74 73 28 6c | 6f 6e 67 20 69 6e 74 20 |t_bits(l|ong int |
|00000e30| 2a 61 72 72 61 79 2c 20 | 69 6e 74 20 73 69 7a 65 |*array, |int size|
|00000e40| 29 0a 7b 0a 09 75 6e 73 | 69 67 6e 65 64 20 6c 6f |).{..uns|igned lo|
|00000e50| 6e 67 20 69 6e 74 20 72 | 65 73 75 6c 74 20 3d 20 |ng int r|esult = |
|00000e60| 30 3b 0a 09 69 6e 74 20 | 69 3b 0a 0a 09 66 6f 72 |0;..int |i;...for|
|00000e70| 28 69 20 3d 20 30 3b 20 | 69 20 3c 20 73 69 7a 65 |(i = 0; |i < size|
|00000e80| 3b 20 69 2b 2b 29 20 7b | 0a 09 09 66 6f 72 28 6a |; i++) {|...for(j|
|00000e90| 20 3d 20 30 3b 20 6a 20 | 3c 20 73 69 7a 65 6f 66 | = 0; j |< sizeof|
|00000ea0| 28 6c 6f 6e 67 20 69 6e | 74 29 2a 43 48 41 52 5f |(long in|t)*CHAR_|
|00000eb0| 42 49 54 3b 20 6a 2b 2b | 29 20 7b 0a 09 09 09 69 |BIT; j++|) {....i|
|00000ec0| 66 28 28 61 72 72 61 79 | 5b 69 5d 20 3e 3e 20 6a |f((array|[i] >> j|
|00000ed0| 29 20 26 20 31 29 09 72 | 65 73 75 6c 74 2b 2b 3b |) & 1).r|esult++;|
|00000ee0| 0a 09 09 7d 0a 09 7d 0a | 09 72 65 74 75 72 6e 20 |...}..}.|.return |
|00000ef0| 72 65 73 75 6c 74 3b 0a | 7d 0a 0a 49 74 20 6d 69 |result;.|}..It mi|
|00000f00| 67 68 74 20 62 65 20 61 | 20 62 69 74 20 66 61 73 |ght be a| bit fas|
|00000f10| 74 65 72 20 69 66 20 79 | 6f 75 20 63 68 61 6e 67 |ter if y|ou chang|
|00000f20| 65 20 74 68 65 20 69 66 | 20 73 74 61 74 65 6d 65 |e the if| stateme|
|00000f30| 6e 74 20 74 6f 3a 0a 0a | 09 09 09 69 66 28 61 72 |nt to:..|...if(ar|
|00000f40| 72 61 79 5b 69 5d 20 26 | 20 28 31 4c 20 3c 3c 20 |ray[i] &| (1L << |
|00000f50| 6a 29 29 09 72 65 73 75 | 6c 74 2b 2b 3b 0a 0a 62 |j)).resu|lt++;..b|
|00000f60| 75 74 20 74 68 61 74 20 | 64 65 70 65 6e 64 73 20 |ut that |depends |
|00000f70| 6f 6e 20 74 68 65 20 70 | 72 6f 63 65 73 73 6f 72 |on the p|rocessor|
|00000f80| 2e 20 47 65 6e 65 72 61 | 6c 2c 20 66 6f 72 20 35 |. Genera|l, for 5|
|00000f90| 30 20 65 6c 65 6d 65 6e | 74 73 2c 20 69 74 20 73 |0 elemen|ts, it s|
|00000fa0| 68 6f 75 6c 64 20 0a 6d | 61 6b 65 0a 6e 6f 20 64 |hould .m|ake.no d|
|00000fb0| 69 66 66 65 72 65 6e 63 | 65 20 62 75 74 20 74 68 |ifferenc|e but th|
|00000fc0| 65 20 66 69 72 73 74 20 | 6d 65 74 68 6f 64 20 69 |e first |method i|
|00000fd0| 73 20 70 72 6f 62 61 62 | 6c 79 20 74 68 65 20 66 |s probab|ly the f|
|00000fe0| 61 73 74 65 72 2e 0a 0a | 0a 2a 2a 2a 0a 0a 41 67 |aster...|.***..Ag|
|00000ff0| 61 69 6e 20 74 68 61 6e | 6b 73 20 74 6f 20 61 6c |ain than|ks to al|
|00001000| 6c 20 77 68 6f 20 72 65 | 70 6c 69 65 64 2c 20 49 |l who re|plied, I|
|00001010| 74 20 77 61 73 20 6d 75 | 63 68 20 61 70 70 72 65 |t was mu|ch appre|
|00001020| 63 69 61 74 65 64 2e 20 | 20 42 54 57 20 49 27 76 |ciated. | BTW I'v|
|00001030| 65 0a 73 65 74 74 6c 65 | 64 20 66 6f 72 20 74 68 |e.settle|d for th|
|00001040| 65 20 6c 6f 6f 6b 75 70 | 20 74 61 62 6c 65 2e 0a |e lookup| table..|
|00001050| 0a 52 6f 79 0a 0a 2d 2d | 20 0a 2d 3d 3d 2d 0a 52 |.Roy..--| .-==-.R|
|00001060| 6f 79 20 4c 65 6f 6e 61 | 72 64 20 20 20 20 20 20 |oy Leona|rd      |
|00001070| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 2b |        |       +|
|00001080| 20 52 6f 79 2e 4c 65 6f | 6e 61 72 64 40 66 65 72 | Roy.Leo|nard@fer|
|00001090| 72 6f 74 65 63 2e 69 65 | 0a 44 65 76 65 6c 6f 70 |rotec.ie|.Develop|
|000010a0| 6d 65 6e 74 20 45 6e 67 | 69 6e 65 65 72 20 20 20 |ment Eng|ineer   |
|000010b0| 20 20 20 20 20 20 20 20 | 20 2b 20 54 65 6c 3a 20 |        | + Tel: |
|000010c0| 2b 33 35 33 2d 31 2d 32 | 39 35 2d 32 35 32 39 0a |+353-1-2|95-2529.|
|000010d0| 46 65 72 72 6f 74 65 63 | 20 4c 74 64 20 20 20 20 |Ferrotec| Ltd    |
|000010e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|000010f0| 2b 20 46 61 78 3a 20 2b | 33 35 33 2d 31 2d 32 39 |+ Fax: +|353-1-29|
|00001100| 35 2d 33 36 32 35 0a 53 | 74 69 6c 6c 6f 72 67 61 |5-3625.S|tillorga|
|00001110| 6e 20 49 6e 64 75 73 74 | 72 69 61 6c 20 50 61 72 |n Indust|rial Par|
|00001120| 6b 2c 20 20 20 20 20 2b | 0a 53 74 69 6c 6c 6f 72 |k,     +|.Stillor|
|00001130| 67 61 6e 2c 20 44 75 62 | 6c 69 6e 2c 20 49 72 65 |gan, Dub|lin, Ire|
|00001140| 6c 61 6e 64 20 20 20 20 | 20 2b 0a 2d 3d 3d 2d 0a |land    | +.-==-.|
|00001150| 0a 0a                   |                         |..      |        |
+--------+-------------------------+-------------------------+--------+--------+